# Copyright (c) 2006 "Gardiner"
# 
# Permission is hereby granted, free of charge, to any person obtaining a copy of
# this software and associated documentation files (the "Software"), to deal in
# the Software without restriction, including without limitation the rights to
# use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
# of the Software, and to permit persons to whom the Software is furnished to do
# so, subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be included in all
# copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.

require 'enumerator'

module EvolutionaryAlgorithm
	attr :population
	attr :selector
	attr :recombinator
	attr :mutator
	
	attr :mutate_chance
	
	# Run the EA for the specified number of generations
	def iterate(generations, quiet = true)
		raise "No recombinator method specified" if !recombinator
		raise "No selector method specified" if !selector
	
		generations.times do |gen|
			# Select the candidates for reproduction
			# We're assuming the recombinator takes 2 individuals and returns 1
			# TODO: Don't assume
			newPop = selector.call(@population, @population.length*2)
	
			# Perform recombination
			# Take 2 individuals at a time and push whatever results
			recombinedPop = []
			
			newPop.each_slice(2) {|ind1, ind2|
				if ind2
					recombinedPop.push(recombinator.call(ind1, ind2))
				else
					recombinedPop.push(ind1)
				end
			}

			# Perform mutation
			if mutator && mutate_chance
				recombinedPop.each_with_index {|ind, idx|
					if rand < @mutate_chance
						recombinedPop[idx] = mutator.call(ind)
					end
				}
			end

			@population = recombinedPop
			
			printf 8.chr*4 + "%3d%", ((gen+1)*100.0/generations).ceil unless quiet
		end
	end
	
	# Prints the top topN members of the population
	# Defaults to the entire population
	def print_population(topN = @population.length)		
		get_best_n(topN).each { |indFit|
				print "#{indFit[1]}\t\t\t\t"
				printf "Score: %f\n", indFit[0]
			}
	end
	
	# Prints the scores of the top topN members of the population
	# Defaults to the entire population
	def print_scores(topN = @population.length)	
		get_best_n(topN).each { |indFit|
				printf "%f\n", indFit[0]
			}
	end
	
	def get_best_n(n)	
		popWithFitness = []
		@population.each {|i| popWithFitness << [get_fitness(i), i] }

		if block_given?
			uniqueBest = []
			
			while uniqueBest.length < n && popWithFitness.length > 0 do
				uniqueBest << popWithFitness.first
				popWithFitness.delete_if {|i| yield(uniqueBest.last, i) }
			end
			
			uniqueBest
		else
			popWithFitness.sort{|a,b| b[0] <=> a[0]}[0..n-1]
		end
	end
	
	# Creates a selector using tournament selection
	def EvolutionaryAlgorithm.make_tournament_selector(tournamentSize, getFitness)
		return Proc.new { |pop, count|
			newPop = []
			
			while newPop.length < count do
				pool = pop.random_elements(tournamentSize)
				fitnesses = pool.collect { |i| getFitness.call(i) }
				newPop.push(pool[fitnesses.max_index()])
			end
			
			newPop
		}
	end
	
	# Don't use - ignores count
	# Creates a selector using unbiased tournament selection
	# Unbiased tournament selection ensures all individuals are sampled
	def EvolutionaryAlgorithm.make_unbiased_tournament_selector(getFitness)
		return Proc.new { |pop, count|
			popWithFitness = pop.collect { |ind| [ind, getFitness.call(ind)] }
			
			newPop = []
			
			tempPopSrc = popWithFitness.clone
			tempPop = []
			
			until tempPopSrc.length == 0 do
				tempPop << tempPopSrc.slice!(rand(tempPopSrc.length))
			end
			
			newPop = Array.parallel_collect(tempPop, popWithFitness) {|a,b|
				if a[1] > b[1]
					a[0]
				else
					b[0]
				end 
			}
			
			newPop
		}
	end
	
	# Creates a selector using fitness proportional (roulette wheel) selection
	def EvolutionaryAlgorithm.make_fitness_proportional_selector(getFitness)
		return Proc.new { |pop, count|
		
			fitnesses = pop.collect { |ind| getFitness.call(ind) }
			offset = 0
			
			# If there are negative fitnesses, we'll add the minimum to all of them
			#  to make them all positive
			if fitnesses.min < 0
				offset = 0 - fitnesses.min
			end
			
			wheel = Array.new(fitnesses.length, 0)
			totalFitness = fitnesses.inject(0.0) {|v,s| s += v + offset}
			prob = 0
			
			# Initialize the wheel
			# Example wheel: 		[0, 0.1, 0.75, 0.9]
			# Respective probabilities:	[0.1, 0.65, 0.15, 0.1]
			fitnesses.each_with_index { |f, idx|
				if idx+1 < wheel.length
					prob += (f + offset) / totalFitness
					wheel[idx+1] = prob
				end
			}
			
			newPop = []
			
			# Do some selecting - pick a number and find the max value less than it			
			while newPop.length < count
				chance = rand
				ind = nil
				
				wheel.each_with_index { |p, idx|
					changed = false
					
					if p < chance
						ind = idx
						changed = true
					end
					
					break unless changed
				}
				
				newPop << pop[ind].clone
			end
			
			newPop
		}
	end
end

